基于堆栈的一位整数中缀表达式计算器, 用C++编写

  1 /*******************************************
  2  * file: stack_cal.cpp
  3  * author: ideawu
  4  * date: 2006-11-17
  5  *******************************************/
  6 
  7 #include <stdio.h>
  8 #include <stdlib.h>
  9 #include <string.h>
 10 
 11 typedef enum{
 12     Token_Error = 0,
 13     Token_Int = 'i',
 14     Token_Div = '/',
 15     Token_Mul = '*',
 16     Token_Sub = '-',
 17     Token_Add = '+',
 18     Token_Mod = '%',
 19     Token_Lp = '(',
 20     Token_Rp = ')'
 21 }TokenType;
 22 
 23 class Token{
 24 public:
 25     int type;
 26     double value;
 27 
 28     Token(){
 29         type = Token_Error;
 30         value = 0;
 31     }
 32 };
 33 
 34 class ArrayStack{
 35 private:
 36     char * name;
 37     Token *tokens;
 38     int size;
 39     int capacity;
 40 
 41 public:
 42     ArrayStack(char* n){
 43         name = n;
 44         size = 0;
 45         capacity = 256;
 46         tokens = new Token[capacity];
 47     }
 48 
 49     ~ArrayStack(){
 50         delete[] tokens;
 51     }
 52 
 53     int getSize(){
 54         return size;
 55     }
 56 
 57     bool isEmpty(){
 58         return (size == 0);
 59     }
 60 
 61     bool isFull(){
 62         return (size == capacity);
 63     }
 64 
 65     void push(Token token){
 66         if(size < capacity){
 67             tokens[size ++] = token;
 68         }else{
 69         }
 70     }
 71 
 72     Token* pop(){
 73         if(size > 0){
 74             size --;
 75             return &tokens[size];
 76         }else{
 77             return NULL;
 78         }
 79     }
 80 
 81     Token* peek(){
 82         if(size > 0){
 83             return &tokens[size-1];
 84         }else{
 85             return NULL;
 86         }
 87     }
 88 
 89     void toString(){
 90         if(size == 0){
 91             printf("%s[0]=\n", name);
 92             return;
 93         }
 94         printf("%s[%d]=", name, size);
 95         printf("(");
 96         printf("{%c,%.4f}", tokens[0].type, tokens[0].value);
 97         for(int i=1; i<size; i++){
 98             printf(", {%c,%.4f}", tokens[i].type, tokens[i].value);
 99         }
100         printf(")\n");
101     }
102 };
103 
104 /*
105  * 归约函数, 从操作数栈和操作符栈各弹出一个元素,
106  * 与操作数栈顶的元素(并未弹出)运算后, 结果存在操作栈顶的元素中.
107  */
108 void calculate(ArrayStack &operandStack, ArrayStack &operatorStack){
109     if(operandStack.getSize() < 2){
110         return;
111     }
112     Token *t1 = operandStack.pop();
113     Token *t2 = operandStack.peek();
114     Token *op = operatorStack.pop();
115     switch(op->type){
116         case '*':
117             t2->value *= t1->value;
118             break;
119         case '/':
120             t2->value /= t1->value;
121             break;
122         case '+':
123             t2->value += t1->value;
124             break;
125         case '-':
126             t2->value -= t1->value;
127             break;
128         default:
129             printf("*********Syntax Error!*********\n");
130             exit(1);
131             break;
132     }
133 }
134 
135 
136 int main(int argc, char *argv[]){
137     char buffer[256];
138     if(argc > 1){
139         strcpy(buffer, argv[1]);
140     }else{
141         printf("Input the statement(1-256 characters):\n");
142         scanf("%s", buffer);
143     }
144 
145     ArrayStack operandStack("operandStack ");
146     ArrayStack operatorStack("operatorStack");
147     int streamLen = strlen(buffer);
148     char c;
149     /*
150      * 需要归约的情况:
151      * 1. 当前的token是整数, 且操作符栈顶元素为'*'或'/';
152      * 2. 当前的token是')';
153      * 3. 当前的token是'+'或'-', 且操作符栈顶元素为'+'或'-';
154      */
155     for(int index=0; index<streamLen; index++){
156         c = buffer[index];
157         Token t;
158         if(c >= '0' && c <= '9'){
159             t.type = Token_Int;
160             t.value = c - '0';
161             operandStack.push(t);
162             if(!operatorStack.isEmpty()){
163                 if(operatorStack.peek()->type == '*'
164                         || operatorStack.peek()->type == '/'){
165                     calculate(operandStack, operatorStack);
166                 }
167             }
168         }else{
169             t.type = c;
170             Token *temp;
171             switch(c){
172                 case ')':
173                     if(operatorStack.isEmpty()){
174                         printf("*********Syntax Error!*********\n");
175                         exit(0);
176                     }
177                     temp = operatorStack.peek();
178                     if(temp->type == '('){
179                         // 使(int) ==> int, 即去掉整数两边的括号后再归约.
180                         operatorStack.pop();
181                         calculate(operandStack, operatorStack);
182                     }else{
183                         calculate(operandStack, operatorStack);
184                         operatorStack.pop();
185                     }
186                     break;
187                 case '-':
188                 case '+':
189                     if(!operatorStack.isEmpty()){
190                         temp = operatorStack.peek();
191                         if(temp->type == '+' || temp->type == '-'){
192                             calculate(operandStack, operatorStack);
193                         }
194                     }
195                     operatorStack.push(t);
196                     break;
197                 default:
198                     operatorStack.push(t);
199                     break;
200             }
201         }
202     }
203     calculate(operandStack, operatorStack);
204 
205     printf("=%f", operandStack.pop()->value);
206     printf("\n");
207     return 0;
208 }
209